package salesforce;

//LC 450 删除二叉搜索树中的节点

public class DeleteNodeInBST {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 方法定义：返回删除key节点之后，根节点的引用
     * 1、当key > root.val时，在root.right中删除key，同时root.right=delete(root.right, key)
     * 2、当key < root.val时，在root.left中删除key, 同时root.left = delete(root.left, key)
     * 3、当key == root.val时，删除当前节点
     * 3.1、当root左右节点都为空时，直接root==null， return
     * 3.2、当root左节点不为空时，root.val = 左边最大的值leftMax， root.left = delete(root.left，leftMax)
     * 3.3、否则root.val = 右边最小值rightMin，root.right = delete(root.right, rightMin)
     * 4、return root
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null; //这句必须，有可能key值在整个树种都找不到
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        }else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        }else {
            if (root.left == null && root.right == null) {
                return null;
            }else if (root.left != null) {
               int leftMax = leftMaxVal(root);
               root.val = leftMax;
               root.left = deleteNode(root.left, leftMax);
            }else {
                int rightMin = rightMinVal(root);
                root.val = rightMin;
                root.right = deleteNode(root.right, rightMin);
            }
        }
        return root;
    }

    private int leftMaxVal(TreeNode node) {
        TreeNode res = node.left;
        while (res.right != null) {
            res = res.right;
        }
        return res.val;
    }

    private int rightMinVal(TreeNode node) {
        TreeNode res = node.right;
        while (res.left != null) {
            res = res.left;
        }
        return res.val;
    }
}
